import java.util.HashSet;
import java.util.Scanner;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-03-24
 * Time:20:48
 */


public class TestDemo {
    //172. 阶乘后的零
    /**n! 尾零的数量即为 n!n! 中因子 10 的个数，而 10=2×5，
     * 因此转换成求 n!n! 中质因子 2 的个数和质因子 5的个数的较小值。
     由于质因子 5 的个数不会大于质因子 2 的个数，我们可以仅考虑质因子 5 的个数。
     而 n!中质因子 5 的个数等于 [1,n]的每个数的质因子 5 的个数之和，
     我们可以通过遍历 [1,n]的所有 5 的倍数求出。
     */
    public int trailingZeroes(int n) {
        //算一下乘法因子里有多少个5就是了
        //5 10 15 20 包含1个因数为5
        //25 包含 2个因数 5 所以26的答案为4+2=6
        //同理125 包含三个因数为5
        int count  = 0;
        while(n/5 !=0){
            count+=n/5;
            n/=5;
        }
        return count;
    }

    //有假币
    /**
     * 当n = 1时，不需要再称了，它就是假币，总共需要0次
     * 当n = 2时，1、1放天平两端，轻的就是假币，总共需要1次
     * 当n = 3时，随机抽出2个放到天平两端，如果天平平衡，则剩下1个就是假币，
     * 否则天平中较轻的是假币，总共需要1次
     * 当n = 4时，分成1、1、2，天平秤1、1，注意题目要求最短时间，
     * 并且是次数最大的情况，也就是我们需要考虑最坏的情况，第一次1、1重量相等，
     * 接着我们把2分开称，总共需要2次
     * 当n = 5时，分成2、2、1，天平秤2、2，同样考虑最坏的情况，2、2重量相等，
     * 接着我们把2分开称，总共需要2次
     * 当n = 6时，分成2、2、2，天平秤2、2，同样考虑最坏的情况，不管如何，还需要
     * 把2分开称，总共需要2次
     * 当n = 7时，分成2、2、3，天平先称2、2，考虑最坏的情况，重量相等，接着我们就需要
     * 按照n = 3的最优情况称，总共需要2次
     * ...
     * <p>
     * 其中有一个规则，我们每次把n分成是3堆，
     * 如果n % 3 == 0,分成 n/3、 n/3、 n/3三堆， 剩下 n/3
     * 如果n % 3 == 1,分成 n/3、 n/3、1 + (n/3)三堆，最坏剩下 1 + (n/3)
     * 如果n % 3 == 2,分成 n/3、 1 + (n/3)、1 + (n/3)三堆，最坏剩下 1 + (n/3)
     */
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int num = scanner.nextInt();
            if (num == 0) {
                continue;
            }
            int count = 0;
            while (num > 1) {
                //每次取1/3,如果不能整除3，有两种情况
                //剩余1个，分成 1/3 、1/3 、1 + (1/3) ，两个1/3放入天平两端，
                //剩余2个，分成 1/3 、1 + (1/3) 、 1 + (1/3)，两个1 + (1/3)放入天平两端
                //由于题目要求最快的时间，并且是求最多的次数，因此取每次剩余的最大值 1 + (1/3)
                count++;
                if (num % 3 == 0) {
                    num /= 3;
                } else {
                    num = num / 3 + 1;
                }
            }
            System.out.println(count);
        }
    }

    //求正数数组的最小不可组成和
    public static void main(String[] args) {
        int[] num = {3,2,5};
        System.out.println(getFirstUnFormedNum(num));
    }

    // i 代表物品
    // j 代表背包容量
    public static int getFirstUnFormedNum(int[] arr) {
        //min为最轻物品的重量，sum为所有物品总重量
        //假设有一个能装入容量为C(C在[min,sum]间取值)的背包
        //arr数组中就是物品的重量;
        //求min~sum中那个容量的背包是不能恰好被从arr数组中挑选出来的物品装满的-找出最小不能被填满的背包
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
            max += arr[i];
        }
        boolean[] dp = new boolean[max + 1];
        //初始化
        dp[0] = true;
        for (int i = 0; i < arr.length; i++) {
            //判断某一物品能否放入时直接忽略容量小于该物品质量的情况
            for (int j = max; j >= arr[i]; j--) {
                //逆序判断背包承重中能够放入的数据
                dp[j] = dp[j-arr[i]] || dp[j];
            }
        }
        for (int i = min;i<dp.length;i++){
            if (!dp[i]){
                return i;
            }
        }
        return max+1;
    }
}
